//Cracking the coding interview (5th), 2_4
//Given a circular linked list, implement an algorithm which returns the node at the beginning of the loop.
//DEFINITION
//Circular linked list: A (corrupt) linked in which a node's next pointer points to an earlier node, soas to make aloop in the linked list.
//EXAMPLE
//Input: A->B->C->D->D->C [the same C as earlier]
//Output: C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _data {
    int data;
    struct _data * next;
} DATA;

DATA* LoopEntrance (DATA *head)
{
    DATA *p, *p2;

    p = p2 = head;
    do
    {
        p = p->next;
        p2 = p2->next->next;
    }
    while (p != p2);
    p = head;
    while (p != p2)
    {
        p = p->next;
        p2 = p2->next;
    }
    return p;
}

void main ()
{
    int cnt;
    DATA *pa, *p, *pp, *tail;

    pa = (DATA *) malloc (sizeof(DATA));

    p = pa;
    p->data = 1;
    p->next = (DATA *) malloc (sizeof(DATA));
    p = p->next;
    p->data = 2;
    p->next = (DATA *) malloc (sizeof(DATA));
    p = p->next;
    p->data = 3;
    p->next = (DATA *) malloc (sizeof(DATA));
    p = p->next;
    p->data = 4;
    p->next = (DATA *) malloc (sizeof(DATA));
    p = p->next;
    p->data = 5;
    p->next = (DATA *) malloc (sizeof(DATA));
    p = p->next;
    p->data = 6;
    pp = p;
    p->next = (DATA *) malloc (sizeof(DATA));
    p = p->next;
    p->data = 7;
    p->next = pp;

    printf ("%x\n", LoopEntrance(pa) - pp);

    tail = pp;
    pp = NULL;
    p = pa;
    cnt = 1;
    while (p)
    {
        if (p == tail)
        {
            if (cnt)
            {
                cnt--;
            }
            else
            {
                break;
            }
        }
        pp = p;
        p = p->next;
        free (pp);
    }
}
